java谷歌Foobar数字站
我正试图解决google foobar的一个挑战,但我被困在如何将其更改为使用递归的问题上。任何指示都会有帮助
public static int[] answer(int[] l, int t) {
// convert the array into a list
List<Integer> list = new ArrayList<>();
for (int i : l) {
list.add(i);
}
for (int i = 0; i < list.size(); i++) {
Integer n = list.get(i);
if (i >= 1) {
Integer nMinus1 = list.get(i - 1);
Integer nMinus2;
Integer nMinus3;
Integer nMinus4;
Integer nMinus5;
Integer nMinus6;
if (n + nMinus1 == t) {
// done
return new int[]{i - 1, i};
} else if (i >= 2) {
nMinus2 = list.get(i - 2);
if (n + nMinus1 + nMinus2 == t) {
// done
return new int[]{i - 2, i};
} else if (i >= 3) {
nMinus3 = list.get(i - 3);
if (n + nMinus1 + nMinus2 + nMinus3 == t) {
// done
return new int[]{i - 3, i};
} else if (i >= 4) {
nMinus4 = list.get(i - 4);
if (n + nMinus1 + nMinus2 + nMinus3 + nMinus4 == t) {
// done
return new int[]{i - 4, i};
} else if (i >= 5) {
nMinus5 = list.get(i - 5);
if (n + nMinus1 + nMinus2 + nMinus3 + nMinus4 + nMinus5 == t) {
// done
return new int[]{i - 5, i};
} else if (i >= 6) {
nMinus6 = list.get(i - 6);
if (n + nMinus1 + nMinus2 + nMinus3 + nMinus4 + nMinus5 + nMinus6 == t) {
// done
return new int[]{i - 6, i};
}
}
}
}
}
}
}
}
return new int[]{-1, -1};
}
问题是:
给定列表l为[4,3,5,7,8],键t为12,函数answer(l,t)将返回列表[0,2],因为列表l包含从索引0开始到索引2结束的子列表[4,3,5],其中4+3+5=12,即使列表(5+7)中后面出现的序列更短。另一方面,给定列表l为[1,2,3,4],键t为15,函数answer(l,t)将返回[-1,-1],因为列表l的子列表中没有可求和为给定目标值t=15的子列表
# 1 楼答案
你可能不需要arraylist。可以对数组l执行双循环。为什么需要递归
你可以这样做:
# 2 楼答案
刚刚提交了我的解决方案。。它被接受了,所以我知道它被谷歌接受了:
(我相信这将比上述解决方案略快,因为如果目标大于数组中所有数字的总和,它将打破循环并返回。)